package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 2020-11-04 11:55
 *
 * https://leetcode-cn.com/problems/trapping-rain-water/
 */
public class _42_接雨水_左到右_右到左_02 {

    public int trap(int[] height) {

        if (height == null || height.length <= 2) {

            return 0;
        }


        int sum = 0;

        int[] leftMaxs = new int[height.length];
        int[] rightMaxs = new int[height.length];


        for (int i = 1; i < height.length; i++) {

            if (leftMaxs[i - 1] < height[i -1]) {

                leftMaxs[i] = height[i - 1];
            }else {

                leftMaxs[i] = leftMaxs[i - 1];
            }
        }

        for (int i = height.length - 2; i >= 0 ; i--) {

            if (rightMaxs[i + 1] < height[i + 1]) {

                rightMaxs[i] = height[i + 1];
            }else {

                rightMaxs[i] = rightMaxs[i + 1];
            }
        }


        for (int i = 0; i < height.length; i++) {

            int h = height[i];

            int min = Math.min(leftMaxs[i], rightMaxs[i]);

            if (h < min) {

                sum += (min - h);
            }

        }

        return sum;
    }
}
